package Q1;

import java.util.Scanner;

public class Main {

    public static int n;
    public static int m;
    public static int ret;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt(); //气球种数
        m = scanner.nextInt(); //气球个数

        dfs(0, new int[m]);

        System.out.println(ret);
    }

    /**
     *
     * @param count
     * @param arr 存放气球的种类
     */
    public static void dfs(int count, int[] arr) {
        if (count == m) {
            for (int i = 1; i < m; i++) {
                if (arr[i] == arr[i - 1]) {
                    return;
                }
            }

            ret = (ret + 1) % 109;
            return;
        }

        for (int i = 1; i <= n; i++) {
            arr[i] = i;
            dfs(count + 1, arr);

            //回溯
            arr[count] = 0;
        }
    }
}
